package com.wrial.middle;
/*
 * @Author  Wrial
 * @Date Created in 9:48 2020/4/3
 * @Description 三角形最小路径和
 */

import java.util.List;

public class LeetCode_120 {

    // 1.使用递归 2.使用记录递归 3.使用动态规划
/*    public int minimumTotal(List<List<Integer>> triangle) {

        return helper(0, 0, triangle);

    }

    private int helper(int i, int j, List<List<Integer>> triangle) {
        // 如果递归到最后一行那必然是结束了
        if (i == triangle.size() - 1) return triangle.get(i).get(j);
        // 其他行的话都会有下和右下
        int left = i + 1;
        int right = j + 1;
        //  每次求得选择最小的
        return Math.min(helper(left, j, triangle), helper(left, right, triangle)) + triangle.get(i).get(j);
    }

*/
    // 2. 使用记忆化搜索  将递归的值记录起来，避免重复计算

    /*   int size;
       int[][] memo;

       public int minimumTotal(List<List<Integer>> triangle) {
           size = triangle.size();
           memo = new int[size][size];
           return helper(0, 0, triangle);

       }

       private int helper(int i, int j, List<List<Integer>> triangle) {
           if (memo[i][j] != 0) return memo[i][j];
           if (i == triangle.size() - 1) return memo[i][j] = triangle.get(i).get(j);
           int left = i + 1;
           int right = j + 1;
           memo[i][j] = Math.min(helper(left, j, triangle), helper(left, right, triangle)) + triangle.get(i).get(j);
           return memo[i][j];
       }
     */
    // 3. 使用动态规划   也可以使用一个一维数组来表示当前层的值，下面的值作废，直到结束（第一行第一个）
    public int minimumTotal(List<List<Integer>> triangle) {

        // 因为最后一行不用调整
        for (int i = triangle.size() - 2; i >= 0; i--) {
            List<Integer> tempList = triangle.get(i);
            for (int j = 0; j < tempList.size(); j++) {
                int min = Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)) + triangle.get(i).get(j);
                triangle.get(i).set(j, min);
            }
        }
        return triangle.get(0).get(0);

    }
}
